package com.lizk.leetcode.sum3_closest;

import com.google.common.collect.Lists;
import org.apache.commons.lang3.ArrayUtils;

import java.util.Arrays;

public class Sum3Closest {
    public static void main(String[] args) {
        Sum3Closest sum3Closest = new Sum3Closest();
        int[] nums = ArrayUtils.addAll(new int[0], -1,2,1,-4);
        System.out.println(sum3Closest.threeSumClosest(nums, 1));
    }


    /**
     * 排序加双指针实现
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest2(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        int sum = 0;
        int start = 0;
        int end = 0;
        for(int i=0;i<nums.length-2;i++) {
            start = i+1;
            end = nums.length - 1;
            while(start < end) {
                sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;

    }

    /**
     * 暴力破解法
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        int tmpNum;
        int result = 0;
        int resultSub = Integer.MAX_VALUE;
        int tmpSub;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i+1; j < nums.length; j++) {
                for (int m = j+1; m < nums.length; m++) {
                    tmpNum = nums[i] + nums[j] +nums[m];
                    tmpSub = tmpNum - target;
                    if (tmpSub < 0){
                        tmpSub =   -tmpSub;
                    }
                    if (tmpSub < resultSub){
                        result = tmpNum;
                        resultSub = tmpSub;
                    }
                }
            }
        }
        return result;
    }
}
